package com.lw.leetcode.add.e;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1449. 数位成本和为目标值的最大数字
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/28 14:10
 */
public class LargestNumber {


    public static void main(String[] args) {
        LargestNumber test = new LargestNumber();

        // 7772
//        int[] cost = {4, 3, 2, 5, 6, 7, 2, 5, 5};
//        int target = 9;

        // 7772
//        int[] cost = {4, 3, 2, 5, 6, 7, 2, 5, 5};
//        int target = 5000;

        // "5555443222"
        int[] cost = {1000, 30, 105, 70, 42, 1000, 1000, 1000, 1000};
        int target = 503;

        // 85
//        int[] cost = {7, 6, 5, 5, 5, 6, 8, 7, 8};
//        int target = 12;

        // 0
//        int[] cost = {2, 4, 6, 2, 4, 6, 4, 4, 4};
//        int target = 5;

        // 32211
//        int[] cost = {6, 10, 15, 40, 40, 40, 40, 40, 40};
//        int target = 47;

        String s = test.largestNumber(cost, target);
        System.out.println(s);
    }

    public String largestNumber(int[] cost, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int length = cost.length;
        for (int i = 0; i < length; i++) {
            map.put(cost[i], i + 1);
        }
        int size = map.size();
        int[] arr = new int[size];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            arr[i++] = entry.getKey();
        }
        Arrays.sort(arr);
        if (arr[0] > target) {
            return "0";
        }
        int[] counts = new int[target + 1];
        counts[arr[0]] = 1;
        counts[0] = 1;
        for (i = arr[0] + 1; i <= target; i++) {
            for (int v : arr) {
                if (i - v < 0) {
                    break;
                }
                if (counts[i - v] == 1) {
                    counts[i] = 1;
                    break;
                }
            }
        }
        if (counts[target] == 0) {
            return "0";
        }
        int[] items = new int[size];
        while (target > 0) {
            for (int j = 0; j < size; j++) {
                int index = target - arr[j];
                if (index >= 0 && counts[index] == 1) {
                    items[j]++;
                    target = index;
                    break;
                }
            }
        }
        int[][] arrs = new int[size][2];
        for (i = 0; i < size; i++) {
            int[] ints = arrs[i];
            ints[0] = map.get(arr[i]);
            ints[1] = items[i];
        }
        Arrays.sort(arrs, (a, b) -> Integer.compare(b[0], a[0]));
        int len = 0;
        for (int item : items) {
            len += item;
        }
        StringBuilder sb = new StringBuilder(len);
        for (int[] ints : arrs) {
            for (int a = ints[1]; a > 0; a--) {
                sb.append(ints[0]);
            }
        }
        return sb.toString();
    }

}
